/**
 * 148. 排序链表
 * https://leetcode-cn.com/problems/sort-list/
 */

const { displayListNode, createListNode, ListNode } = require('../../libs/public');

// /**
//  * @param {ListNode} head
//  * @return {ListNode}
//  */
// function sortList(head) {
//   if (!head) return head;
//   const cache = [];
//   let node = head;
//   while (node) {
//     cache.push(node);
//     node = node.next;
//   }
//   cache.sort((a, b) => a.val - b.val);
//   const lastIndex = cache.length - 1;
//   for (let i = 0; i < lastIndex; i += 1) {
//     cache[i].next = cache[i + 1];
//   }
//   cache[lastIndex].next = null;
//   return cache[0];
// }

/**
 * @param {ListNode} head1
 * @param {ListNode} head2
 * @return {ListNode}
 */
function merge(head1, head2) {
  if (!head1) return head2;
  if (!head2) return head1;
  let head;
  let node1 = head1;
  let node2 = head2;
  if (node1.val < node2.val) {
    head = node1;
    node1 = node1.next;
  } else {
    head = node2;
    node2 = node2.next;
  }
  let node = head;
  while (node1 && node2) {
    if (node1.val < node2.val) {
      node.next = node1;
      node1 = node1.next;
    } else {
      node.next = node2;
      node2 = node2.next;
    }
    node = node.next;
  }
  if (node1) {
    node.next = node1;
  } else if (node2) {
    node.next = node2;
  }
  return head;
}

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function sortList(head) {
  if (!head || !head.next) return head;
  let length = 0;
  let node = head;
  while (node) {
    length += 1;
    node = node.next;
  }
  const dummyHead = new ListNode(0, head);
  for (let splitCount = 1; splitCount < length; splitCount <<= 1) {
    let prev = dummyHead;
    node = prev.next;
    while (node) {
      const head1 = node;
      for (let i = 1; i < splitCount && node.next; i += 1) {
        node = node.next;
      }
      const head2 = node.next;
      node.next = null;
      node = head2;
      for (let i = 1; i < splitCount && node && node.next; i += 1) {
        node = node.next;
      }
      let next = null;
      if (node) {
        next = node.next;
        node.next = null;
      }
      prev.next = merge(head1, head2);
      while (prev.next) {
        prev = prev.next;
      }
      node = next;
    }
  }
  return dummyHead.next;
}

console.log(displayListNode(sortList(createListNode([4, 2, 1, 3]))) === '[1,2,3,4]');
console.log(displayListNode(sortList(createListNode([-1, 5, 3, 4, 0]))) === '[-1,0,3,4,5]');
console.log(displayListNode(sortList(createListNode([]))) === '[]');
